Telecommunication protocols often use transactions that involve the exchange of messages between two entities, such as a query sent from a client node A to a server node B followed by a response sent from node B back to node A, or a command sent from A to B followed by an acknowledgement of that command sent from B to A. As used herein, the term “transaction” broadly refers to an interaction between two entities, which may be, but are not limited to, two nodes in a network, two networks, two hardware modules within a frame, two software applications within a node, two modules within an application, and so on.
In an example scenario, node A will usually include in the first message some unique identifier that will also appear in the response, which node A can then use to correlate responses with their respective requests. This requires node A to maintain a repository of transaction records associated with these unique identifiers. When sending a query, node A will insert a record into the transaction repository. Upon receipt of a response message, node A will usually need to search this repository to see which query, if any, the message is a response to, and then subsequently process the response message and purge the corresponding record. In addition, transactional protocols often need the ability to sequentially traverse transaction records in some pre-determined order (e.g. transaction expiration time).
Thus, it is desirable to keep the list of unique identifiers in a data structure that supports insertion, deletion, traversal, modification, and searching. Both arrays and linked lists are well suited for sequential traversal of their elements, but each has advantages and disadvantages.
An array, for example, can be indexed so that it can be searched quickly, which makes arrays well suited for direct access. Inserting an element into an array or deleting an element from an array, however, are expensive operations because they require adjacent elements to be relocated to make space for the inserted element or to close up the space left behind by a deleted element.
Doubly-linked lists, on the other hand, are well suited for insertion and deletion. They are not indexed, however, and thus searching a linked list involves stepping through the list element by element until the desired element is found, which can take more time as the linked list increases in length. Where linked lists are used, the elements to be added to a linked list are typically allocated on an as-needed basis, i.e., dynamically. Each member of a linked list typically includes pointers to other members.
Thus, what is needed is a data structure that can support both “array-like” operations such as indexing and searching and “list-like” operations such as insertion, deletion, and reordering. Such a data structure is referred to as a “multi-view” data construct, since it would allow data to be indexed as if it were contained within array but also support insert, delete, and reorder operations as if it were a linked list. The above operations also have applicability to database solutions that require multiple views into the database schema.
In some applications, such as telecommunications applications and database solutions, for example, it may be possible that the elements of a data structure may be operated upon by multiple entities simultaneously. Thus, the data construct must be capable of being used concurrently while maintaining data integrity.
A common approach to supporting concurrent access is to use locks so that only one entity at a time may change the data contained within the data structure. Lock-based synchronization commonly uses a data construct called a mutual-exclusion flag, or “mutex”, to indicate whether a data structure is currently in use or available. Locks have disadvantages, however. In one approach, the entire data structure is locked when an entity is manipulating any element in the structure, which is easy to implement but which can stall operations by other entities, even when the other entity wants to manipulate a different element than the one being currently manipulated. Another approach is to lock only the element being manipulated, which is less likely to stall other entities but which is inefficient and complicated to implement, especially for insertion and deletion in a linked list, as these operations typically involve the modification of more than one linked list element. This approach also relies on system-level locks: when multiple threads attempt to use the same mutex, the operating system kernel must arbitrate between the threads. This kernel-level arbitration is computationally expensive and can become a system bottleneck during periods of peak activity. Thus, what is needed is a multi-view data construct that supports concurrent access in a lock-free manner.
Yet another issue that a multi-view construct that supports concurrent access must address is management of the life-cycle of an element, defined herein as the time from when an element is allocated to the time that the element is released. Since each member of a linked list can be pointed to by other members, before a dynamically allocated member of a linked list can be released, the system must ensure that nothing is pointing to that member. This is of particular concern in a multithreaded system or other application where a member may be accessed or otherwise processed by more than one entity, sometimes simultaneously or near-simultaneously. Thus, multi-view constructs that support linked lists must address the two-fold problem of keeping track of an element's presence in a list (managing list membership) and also mediating attempts by multiple entities to access the same element (managing access.)
One conventional technique for managing these twin problems, which stores in each member a number that indicates how many other members are pointing to or accessing that member, is unworkable for dynamically allocated linked lists. In this technique, which is called “reference counting”, an element in a linked list can be released only if its reference count=0 (signifying that no other element links to that member and that the element is not currently being accessed by any entity.) Once the element is released, however, the reference count disappears along with the element. To overcome that problem, another approach was developed that stores information outside of the members themselves, using data constructs called “hazard pointers”, which are a list of pointers to elements that are in use. When an element is no longer being accessed its entry is removed from the hazard pointer list. This requires the maintenance of one or more lists to hold the hazard pointers. Thus, what is needed is a lock-free multi-view construct that is compatible with methods for managing element life-cycles.
Thus, in light of the disadvantages associated with conventional implementations of multi-view data constructs, there exists a need for an alternative approach to implement multi-view data constructs that support “lock-free” operations (e.g., operations that do not use mutexes) and direct access.